6.1 图的基本概念与表示
图相较于二叉树又是另一种结构，从名称就可以看出，图是另一种复杂的数据结构。
图在我们的实际应用中还是比较广泛的，本节我们将针对图的基本概念、Go语言的实现进行讲解。
本节代码存放目录为 lesson12
概念与原理
图 是一种用于表示对象之间关系的数据结构，它由顶点（节点，Vertex）和边（Edge）组成，常用于表示网络、路径、关系等问题。
基本结构如下所示：
A --- B
\ /
C
其中A、B、C就是节点，连接的线就是边。
我们可以将图表示为 ( G = (V, E) )，其中：
V 是顶点的集合。
E 是边的集合，表示顶点之间的关系。
图的分类
图可以根据边的方向分为有向图、无向图；通过边是否有权重分为无权图、带权图。
无向图和有向图
无向图：边没有方向箭头，表示顶点之间的关系是双向的。
A --- B \ / C在无向图中，
A、B、C之间的关系是双向的，例如A和B可以互相访问。有向图：边有方向箭头，表示顶点之间的关系是单向的。
A ---> B ^ / \ v C在有向图中，边是有方向的，表示
A可以到达B，但B不一定能到达A。同样，C指向A，表示从C可以到达A。
带权图和无权图
无权图：边没有权重，表示单纯的连接关系。
A --- B \ / C无权图中的边仅表示顶点之间的连接关系，没有附加的权重信息。
带权图：边上附有权重，表示顶点之间的具体关系，如距离、成本等。
A --(3)--> B \ / (1) (2) C <--- D在带权图中，边上附有数字权重，表示从一个顶点到另一个顶点的代价或距离。例如，从
A到B的边有权重3，从C到D的边有权重1。
图的表示方法
邻接矩阵
邻接矩阵是一种常用的图表示方法。它使用一个二维数组来表示图，行和列分别代表顶点，矩阵中的值表示顶点之间是否有边相连。
如果有边相连，则对应位置的值为 1（或权重值）；如果没有边相连，则值为 0。
换句话说，如果是无向的，那么值就是1，比如A-B，那么AB值就是1，BA值也是1；如果是有向的A->B，但是B到A没有指向，那么AB就是1，BA就是0。
如果是有权重的，比如权重是5，那么A->B，AB值就是5。
无向无权图的邻接矩阵表示如下：
图结构：
A --- B
\ /
C
矩阵表示：
A B C
A [0, 1, 1]
B [1, 0, 1]
C [1, 1, 0]
行和列分别对应顶点
A、B、C，其中行表示出发顶点，列表示到达顶点。数组索引
[0][1] = 1表示A和B之间有边相连。对于无向图，矩阵是对称的。
总的来说，就是通过矩阵来实现对应关系的记录，比如上面的示意图中，我们就可以通过：[0][1] 得到 AB 关系，通过 [0][2] 得到 AC 关系，通过 [1][2] 得到 BC 关系。
那么同理我们可以得出 有向无权图的矩阵表示：
图结构：
A ---> B
^ /
\ v
C
矩阵表示：
A B C
A [0, 1, 0]
B [0, 0, 1]
C [1, 0, 0]
在上面的表示中，[0][1] 即AB 有向值为 1，[1][2] 即 BC有向值为 1，[2][0] 即 AC 有向值为 1。
我们在上面的有向图中加上权重。则有向有权图矩阵表示如下：
图结构：
(2)
A --> B
^ / (5)
\ v
C
矩阵表示：
A B C
A [0, 2, 0]
B [0, 0, 5]
C [1, 0, 0]
在上面的结构中，AB 有向，权重为 2，所以 [0][1] 值为 2；BC 有向，权重为 5，所以 [1][2] 值为 5。
邻接表
邻接表是另一种常用的图表示方法。它使用链表或数组来表示每个顶点的相邻顶点，对于每个顶点，列出它的所有相邻顶点。
邻接表特别适合稀疏图（即边相对较少的图），因为它比邻接矩阵节省空间。
无向图的邻接表表示如下：
图结构：
A --- B
\ /
C
邻接表示：
A: B, C
B: A, C
C: A, B
上图表示顶点 A 与顶点 B 和 C 相连；顶点 B 与 A 和 C 相连；顶点 C 与顶点 A 和 B 相连。
有向图的邻接表表示如下：
图结构：
A ---> B
^ /
\ v
C
邻接表示：
A: B
B: C
C: A
上面的结构中，由于是有向表，所以只有表示关系就更加简单一些，A 节点指向了 B 节点，所以在邻接表中是这样：A: B
也就是说邻接表其实就是将指向关系给罗列了出来，或者说将图结构给直接就写出来了。
有向有权图的邻接表表示如下：
图结构：
(2)
A --> B
^ / (5)
\ v
C
邻接表表示：
A: B (2)
B: C (5)
C: A
有权的表示其实也就是在后面补充上了权重，比如B(2)就表示B->C的权重为2。
Go 语言的实现
在 Go 语言中，图可以通过邻接表或邻接矩阵进行表示。下面是一个基于邻接表的简单无向图实现：
// Graph 定义图结构
type Graph struct {
vertices map[string][]string
}
// NewGraph 创建一个新的图
func NewGraph() *Graph {
return &Graph{
vertices: make(map[string][]string),
}
}
// AddEdge 添加边
func (g *Graph) AddEdge(v1, v2 string) {
g.vertices[v1] = append(g.vertices[v1], v2)
g.vertices[v2] = append(g.vertices[v2], v1)
}
// Print 打印图
func (g *Graph) Print() {
for vertex, edges := range g.vertices {
fmt.Printf("%s -> %v\n", vertex, edges)
}
}
func main() {
graph := NewGraph()
graph.AddEdge("A", "B")
graph.AddEdge("A", "C")
graph.AddEdge("B", "C")
graph.Print()
}
执行结果输出如下所示：
A -> [B C]
B -> [A C]
C -> [A B]
图的Go实现比较简单，就是通过map与切片结合将邻接表输出，邻接矩阵的实现也差不多，邻接矩阵我们可以通过二维数组来进行实现。